package de.riceman.simpleGo.main;
import java.util.AbstractSet;
import java.util.BitSet;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Random;
import org.apache.lucene.util.OpenBitSet;


import javax.activation.UnsupportedDataTypeException;

/**
 * The class BitMatrix.
 * This is the basic datastructure for moves, groups, empty
 * partitions, eyes, etc. as well as for the adjacency
 * relations of the whole board.
 * 
 * @author Mario Reissmann
 */
public class BitMatrix implements Cloneable,
	Iterator<BitMatrix>, Iterable<BitMatrix> {
	
	/** The underlying bit set. */
	private OpenBitSet bitset;

	/** The number of columns. */
	private int columns;
	
	/** The number of rows. */
	private int rows;

	/** The set of child bit matrices used to hold 
	 * real eyes of a group. */
	private AbstractSet<BitMatrix> children;

	/** Pointer for the Iterator implementation. */
	private int itPointer = 0;
	
	/**
	 * Instantiates a new bit matrix.
	 * 
	 * @param size The number of rows or columns.
	 */
	public BitMatrix(int size) {
		
		this.columns = size;
		this.rows = size;

		bitset = new OpenBitSet(size*size);
		children = new HashSet<BitMatrix>();
	}
	
	/**
	 * Instantiates a new bit matrix.
	 * 
	 * @param rows The number of rows.
	 * @param columns The number of columns.
	 */
	public BitMatrix(int rows, int columns) {
		
		this.columns = columns;
		this.rows = rows;
		
		bitset = new OpenBitSet(columns*rows);
		children = new HashSet<BitMatrix>();
	}

	/**
	 * Sets the bit to the specified value.
	 * 
	 * @param i The row index.
	 * @param j The column index.
	 * @param b The boolean value.
	 */
	public void set(int i, int j, boolean b) {

		if (b) {
			bitset.fastSet((i*columns)+j);
		} else {
			bitset.fastClear((i*columns)+j);
		}
	}

	/**
	 * Sets the bit.
	 * 
	 * @param i The index of the bit to set.
	 */
	public void set(int i) {

		set(0, i, true);
	}
	
	/**
	 * Gets the bit.
	 * 
	 * @param i The row index.
	 * @param j The column index.
	 * 
	 * @return true, if bit is set, otherwise false.
	 */
	public boolean get(int i, int j) {

		return bitset.fastGet((i*columns)+j);
	}

	/**
	 * Gets the bit.
	 * 
	 * @param i The index.
	 * 
	 * @return true, if bit is set, otherwise false.
	 */
	public boolean get(int i) {
		
		return bitset.fastGet(i);
	}
	
	/**
	 * Gets the number of columns.
	 * 
	 * @return The number of columns.
	 */
	public int getColumns() {
	
		return columns;
	}

	/**
	 * Gets the number of rows.
	 * 
	 * @return The number of rows.
	 */
	public int getRows() {
	
		return rows;
	}
	
	/**
	 * Gets the children.
	 * 
	 * @return The children.
	 */
	public AbstractSet<BitMatrix> getChildren() {
		
		return children;
	}

	/**
	 * Multiplies BitMatrix a with BitMatrix b.
	 * 
	 * @param a The BitMatrix a.
	 * @param b The BitMatrix b.
	 * 
	 * @return The product of a and b.
	 * 
	 * @throws UnsupportedDataTypeException The UnsupportedDataTypeException.
	 */
	public static BitMatrix multiply(BitMatrix a, BitMatrix b) throws UnsupportedDataTypeException {
		if (b.getRows() != a.getColumns()) {
			throw new UnsupportedDataTypeException("Matrix dimensions are incompatible for multiplication.");
		}
		int j, k;
		/*boolean s;
		BitMatrix n = new BitMatrix(a.getRows(), b.getColumns());
		
		for (j = 0; j < a.getRows(); j++) {
			
			for (k = 0; k < b.getColumns(); k++) {
				s = false;
				for (i = 0; i < a.getColumns(); i++) {
					//s = s || ((a.get(j, i) && b.get(i, k)));
					if ((a.get(j, i) && b.get(i, k))) {
						s = true;
						break;
					}
				}
				n.set(j, k, s);
			}
		}*/
		//System.out.println("---------\n" + a.toString());
		//System.out.println(" * ");
		//System.out.println(b.toString());
		
		//Faster implementation:
		BitMatrix res = new BitMatrix(a.rows, b.columns);
		OpenBitSet n;
		
		//For each row in the result set...
		for(j = 0; j < res.rows; j++) {
			//...and for each column in the result set...
			for(k = 0; k < res.columns; k++) {
				
				//If the bit is set in BitMatrix a... 
				if(a.getRow(j).fastGet(k)) {
					
					//...then unify the current row with the row
					//of BitMatrix b that is related to the current
					//column.
					n = res.getRow(j);
					n.or(b.getRow(k));
					res.setRow(j, n);
				}
			}
		}
		
		return res;
	}
	
	/**
	 * Replaces the k-th row of the BitMatrix.
	 * 
	 * @param k The row index.
	 * @param other The new row.
	 */
	private void setRow(int k, OpenBitSet other) {
		
		for(int i = 0; i < this.columns; i++) {
			if (other.fastGet(i)) {
				this.bitset.fastSet((k*columns)+i);
			} else {
				this.bitset.fastClear((k*columns)+i);
			}
		}
	}
	
	/**
	 * Gets the k-th row of the BitMatrix.  
	 * 
	 * @param k The row index.
	 * @return The row.
	 */
	private OpenBitSet getRow(int k) {
		
		OpenBitSet row = new OpenBitSet((long) this.columns);
		
		int i = k * this.columns;
		
		//Set each bit set in the current BitMatrix between the start
		//index and the last index of the row.
		while((i = this.bitset.nextSetBit(i)) != -1
				&& i < ((k+1)*columns)) {
			row.fastSet(i % this.columns);
			i++;
		}
		
		return row;
	}

	/**
	 * Union with BitMatrix b.
	 * 
	 * @param b The BitMatrix b.
	 * 
	 * @throws UnsupportedDataTypeException The UnsupportedDataTypeException.
	 */
	public void union(BitMatrix b)
			throws UnsupportedDataTypeException {
		
		if (this.getRows() != b.getRows() 
				|| this.getColumns() != b.getColumns()) {
			throw new UnsupportedDataTypeException("Matrix dimensions are incompatible for union.");
		}
		
		this.bitset.union(b.bitset);
	}
	
	/**
	 * Union of BitMatrices a and b.
	 * 
	 * @param a The BitMatrix a.
	 * @param b The BitMatrix b.
	 * 
	 * @return The resulting BitMatrix.
	 * 
	 * @throws UnsupportedDataTypeException The UnsupportedDataTypeException.
	 */
	public static BitMatrix union (BitMatrix a, BitMatrix b)
			throws UnsupportedDataTypeException {
		if (a.getRows() != b.getRows() 
				|| a.getColumns() != b.getColumns()) {
			throw new UnsupportedDataTypeException("Matrix dimensions are incompatible for union.");
		}
		
		BitMatrix n = new BitMatrix(a.getRows(), a.getColumns());
		
		n.bitset = (OpenBitSet) (a.bitset.clone());
		n.bitset.union(b.bitset);
		
		/*for (i = 0; i < a.getRows(); i++) {
			for (j = 0; j < a.getColumns(); j++) {
				n.set(i, j, a.get(i, j) || b.get(i, j));
			}
		}*/
		return n;
	}

	/**
	 * Returns true if this BitMatrix intersects BitMatrix b.
	 * 
	 * @param b The BitMatrix b.
	 * @return True if they intersect, otherwise false.
	 * @throws UnsupportedDataTypeException The unsupported data type exception.
	 */
	public boolean intersects(BitMatrix b) throws UnsupportedDataTypeException {
		if (this.getRows() != b.getRows() || this.getColumns() != b.getColumns()) {
			throw new UnsupportedDataTypeException("Matrix dimensions are incompatible for intersection.");
		}
		
		return this.bitset.intersects(b.bitset);
	}
	
	/**
	 * Intersects this BitMatrix with BitMatrix b.
	 * 
	 * @param b The BitMatrix b.
	 * @throws UnsupportedDataTypeException The unsupported data type exception.
	 */
	public void intersect(BitMatrix b) throws UnsupportedDataTypeException {
		if (this.getRows() != b.getRows() || this.getColumns() != b.getColumns()) {
			throw new UnsupportedDataTypeException("Matrix dimensions are incompatible for intersection.");
		}
		
		this.bitset.intersect(b.bitset);
	}
	
	/**
	 * Intersection of BitMatrix a and b.
	 * 
	 * @param a The BitMatrix a.
	 * @param b The BitMatrix b.
	 * 
	 * @return The resulting BitMatrix.
	 * 
	 * @throws UnsupportedDataTypeException The unsupported data type exception.
	 */
	public static BitMatrix intersection (BitMatrix a, BitMatrix b) throws UnsupportedDataTypeException {
		if (a.getRows() != b.getRows() || a.getColumns() != b.getColumns()) {
			throw new UnsupportedDataTypeException("Matrix dimensions are incompatible for intersection.");
		}
		//int i, j;
		
		BitMatrix n = new BitMatrix(a.getRows(), a.getColumns());
		
		n.bitset = (OpenBitSet) (a.bitset.clone());
		n.bitset.intersect(b.bitset);
		
		/*for (i = 0; i < a.getRows(); i++) {
			for (j = 0; j < a.getColumns(); j++) {
				n.set(i, j, a.get(i, j) && b.get(i, j));
			}
		}*/
		return n;
	}
	
	/**
	 * Xors this BitMatrix with BitMatrix b.
	 * 
	 * @param the BitMatrix B
	 * 
	 * @throws UnsupportedDataTypeException the unsupported data type exception
	 */
	public void xor (BitMatrix b) throws UnsupportedDataTypeException {
		if (this.getRows() != b.getRows() || this.getColumns() != b.getColumns()) {
			throw new UnsupportedDataTypeException("Matrix dimensions are incompatible for xor.");
		}
		
		this.bitset.xor(b.bitset);
	}
	
	/**
	 * Xor.
	 * 
	 * @param a the a
	 * @param b the b
	 * 
	 * @return the bit matrix
	 * 
	 * @throws UnsupportedDataTypeException the unsupported data type exception
	 */
	public static BitMatrix xor (BitMatrix a, BitMatrix b) throws UnsupportedDataTypeException {
		if (a.getRows() != b.getRows() || a.getColumns() != b.getColumns()) {
			throw new UnsupportedDataTypeException("Matrix dimensions are incompatible for xor.");
		}
		
		BitMatrix n = new BitMatrix(a.getRows(), a.getColumns());
		
		n.bitset = (OpenBitSet) (a.bitset.clone());
		n.bitset.xor(b.bitset);

		return n;
	}
	
	/**
	 * Not the matrix :-)
	 * 
	 * @param a the a
	 * @param b the b
	 * 
	 * @return the bit matrix
	 * 
	 * @throws UnsupportedDataTypeException the unsupported data type exception
	 */
	public static BitMatrix not (BitMatrix a) {
		
		BitMatrix n = new BitMatrix(a.getRows(), a.getColumns());
		
		n.bitset = (OpenBitSet) a.bitset.clone();
		
		for (int i = 0; i < a.getRows()*a.getColumns(); i++) {
			n.bitset.fastFlip(i);
		}
		
		return n;
	}
	
	/**
	 * Removes all bits from this BitMatrix where BitMatrix b contains a bit.
	 * 
	 * @param b The BitMatrix b.
	 * 
	 * @throws UnsupportedDataTypeException The unsupported data type exception.
	 */
	public void remove(BitMatrix b) throws UnsupportedDataTypeException {
		if (this.getRows() != b.getRows() || this.getColumns() != b.getColumns()) {
			throw new UnsupportedDataTypeException("Matrix dimensions are incompatible for difference.");
		}
		
		this.bitset.remove(b.bitset);
	}
	
	/**
	 * Removes all bits from BitMatrix a where b contains a bit.
	 * 
	 * @param a The BitMatrix a.
	 * @param b The BitMatrix b.
	 * 
	 * @return The resulting BitMatrix.
	 * 
	 * @throws UnsupportedDataTypeException The unsupported data type exception.
	 */
	public static BitMatrix difference (BitMatrix a, BitMatrix b) throws UnsupportedDataTypeException {
		if (a.getRows() != b.getRows() || a.getColumns() != b.getColumns()) {
			throw new UnsupportedDataTypeException("Matrix dimensions are incompatible for difference.");
		}
		
		BitMatrix n = new BitMatrix(a.getRows(), a.getColumns());
		
		n.bitset = (OpenBitSet) (a.bitset.clone());
		n.bitset.remove(b.bitset);
		
		/*for (i = 0; i < a.getRows(); i++) {
			for (j = 0; j < a.getColumns(); j++) {
				
				if (a.get(i, j) && !b.get(i, j)) {
					n.set(i, j, true);
				}
			}
		}*/
		return n;
	}
	
	/**
	 * Checks if two matrices are connected.
	 * 
	 * @param r The BitMatrix r.
	 * @param s The BitMatrix s.
	 * @param adjacencies The adjacency matrix.
	 * 
	 * @return True, if they are connected, otherwise false.
	 * 
	 * @throws UnsupportedDataTypeException The UnsupportedDataTypeException.
	 */
	public static boolean isConnected(BitMatrix r, BitMatrix s, BitMatrix adjacencies) throws UnsupportedDataTypeException {
		if (r.getRows() != 1 || s.getRows() != 1) {
			throw new UnsupportedDataTypeException("Can only find connections between single row BitMatrices.");
		}
				
		BitMatrix a = BitMatrix.multiply(r, adjacencies);
		
		return a.bitset.intersects(s.bitset);
	}
	
	/**
	 * Returns the distance (shortest path) between the two nodes r and s in the graph
	 * represented by the adjacency matrix.
	 * 
	 * @param r The BitMatrix r.
	 * @param s The BitMatrix s.
	 * @param adjacencies The adjacency matrix.
	 * 
	 * @return The distance between r and s.
	 * 
	 * @throws UnsupportedDataTypeException The UnsupportedDataTypeException.
	 */
	public static int distance(BitMatrix r, BitMatrix s, BitMatrix adjacencies)
			throws UnsupportedDataTypeException {
		
		if (r.getRows() != 1 || s.getRows() != 1) {
			throw new UnsupportedDataTypeException("Can only find connections between single row BitMatrices.");
		}
		
		BitMatrix a = (BitMatrix) r.clone();
		
		int i = 0;
		
		while (true) {
			
			//If no intersection is found, expand the borders of BitMatrix a by 1 and repeat this step.
			if (!a.bitset.intersects(s.bitset)) {
				a = BitMatrix.multiply(a, adjacencies);
				i++;
			} else {
				return i-1;
			}
		}
	}
	
	/**
	 * Checks if this is a zero matrix.
	 * 
	 * @return true, if this is a zero matrix
	 */
	public boolean isZeroMatrix () {
		
		return bitset.isEmpty();
	}
	
	/**
	 * Gets the number of set bits.
	 * 
	 * @return the number of set bits
	 */
	public int getNumberOfSetBits () {
		
		return (int) bitset.cardinality();
	}
	
	/**
	 * Gets the index of the first set bit.
	 * 
	 * @return the index of the first set bit
	 */
	public int getIndexOfFirstSetBit () {
		
		return bitset.nextSetBit(0);
	}
	
	/**
	 * Select random bit from bit matrix. 
	 * This is method used by AI players only and therefore can return a zeromatrix as well, as
	 * a pass is always a regular move.
	 * 
	 * @return the bit matrix
	 */
	public BitMatrix getRandomBitAsBitMatrix() {
		BitMatrix move = new BitMatrix(this.getRows(), this.getColumns());

		int n = this.getNumberOfSetBits();
		
		if (n > 0) {
			
			Random rand = new Random();
			
			//make the pass another virtual bit of the bit matrix
			int randombit = rand.nextInt(n+1);

			if (randombit == n+1) {
				//return a zero matrix (pass)
				return move;
			} else {
				n = 0;
				
				for (int i = 0; i < (this.getRows()*this.getColumns()); i++) {
					if (this.get(i)) {
						if (n == randombit) {
							move.set(i);
							break;
						}
						n++;
					}
				}
			}
		}
		
		return move;
	}
	
	/**
	 * Resets the matrix.
	 */
	public void reset() {
		
		this.bitset = new OpenBitSet(getColumns()*getRows());
	}
	
	
	/**
	 * 
	 * @see java.lang.Object#equals(java.lang.Object)
	 */
	public boolean equals(Object object) {
		if (object instanceof BitMatrix) {
			BitMatrix b = (BitMatrix) object;
			if (this.getRows() != b.getRows() || this.getColumns() != b.getColumns()) {
				return false;
			} else {

				return bitset.equals(b.bitset);
			}
		} else {
			return false;
		}
	}
	
	/**
	 * @see java.lang.Object#toString()
	 */
	@Override
	public String toString() {
		
		String out = new String();
		
		for (int i = 0; i < (columns*rows); i++) {
			
			if (i%columns==0 && i!=0) {
				out = out + "\n";
			}
			out = out + (bitset.get(i) == true ? "1" : "0");
		}
		
		return out;
	}
	
	/**
	 * @see java.lang.Object#clone()
	 */
	public Object clone() {

		Iterator<BitMatrix> it;
		
		BitMatrix clone = new BitMatrix(this.getRows(), this.getColumns());			
		
		clone.bitset = (OpenBitSet) this.bitset.clone();
		
		/*for (i = 0; i < this.getRows(); i++) {
			for (j = 0; j < this.getColumns(); j++) {
				clone.set(i, j, this.get(i, j));
			}
		}*/
		it = this.getChildren().iterator();
		
		while (it.hasNext()) {
			clone.getChildren().add((BitMatrix) it.next().clone());
		}
		
		return clone;
	}

	@Override
	public Iterator<BitMatrix> iterator() {
		// TODO Auto-generated method stub
		this.itPointer = 1;
		return this;
	}

	@Override
	public boolean hasNext() {
		
		//add zero matrix to the set of bits
		if (this.itPointer <= this.getNumberOfSetBits() + 1) {
			return true;
		} else {
			return false;
		}
	}

	@Override
	public BitMatrix next() {
		
		BitMatrix next = new BitMatrix(this.rows, this.columns);
		
		//add zero matrix to the set of bits
		if (itPointer == this.getNumberOfSetBits() + 1) {
			this.itPointer++;
			return next;
		}
		
		int counter = 0;
		
		for (int i = 0; i < (rows*columns); i++) {
			
			if (this.get(i)) {
				counter++;
				if (counter == itPointer) {
					next.set(i);
				}
			}
		}
		this.itPointer++;
		return next;
	}

	@Override
	public void remove() {
		// TODO Auto-generated method stub
		
	}
}
